struct DAG
    blocks
    inmap
    outmap
    adj
    revadj
    inputs
    outputs

    function DAG(blocks)
        _inmap = get_input_map(blocks)
        _outmap = get_output_map(blocks)
        _adj = get_block_adjacency_list(blocks, _inmap)
        _revadj = get_block_reverse_adjacency_list(blocks, _outmap)
        topsort = topological_sort(_adj, _revadj, names=[block.name for block ∈ blocks])

        M = Bijection(Dict(t => i for (i, t) ∈ enumerate(topsort)))

        return new(
            [blocks[t] for t ∈ topsort],
            Dict(k => (M * v) for (k, v) ∈ _inmap),
            Dict(k => (M * v) for (k, v) ∈ _outmap),
            [M * _adj[t] for t ∈ topsort],
            [M * _revadj[t] for t ∈ topsort],
            OrderedSet(k for k ∈ keys(_inmap) if k ∉ keys(_outmap)),
            OrderedSet(keys(_outmap)))
    end
end

function get_input_map(blocks)
    inmap = Dict{String, OrderedSet{Int64}}()
    for (n, block) ∈ enumerate(blocks)
        for i ∈ block.inputs
            inset = get!(inmap, i, OrderedSet{Int64}())
            push!(inset, n)
        end
    end
    return inmap
end

function get_output_map(blocks)
    outmap = Dict{String, Int64}()
    for (n, block) ∈ enumerate(blocks)
        for o ∈ block.outputs
            if o ∈ keys(outmap)
                error("$o is output twice")
            end
            outmap[o] = n
        end
    end
    return outmap
end

function get_block_adjacency_list(blocks, inmap)
    adj = Vector{OrderedSet{Int64}}()
    for block ∈ blocks
        current_adj = OrderedSet{Int64}()
        for o ∈ block.outputs
            if o ∈ keys(inmap)
                current_adj = current_adj ∪ inmap[o]
            end
        end
        push!(adj, current_adj)
    end
    return adj
end

function get_block_reverse_adjacency_list(blocks, outmap)
    revadj = Vector{OrderedSet{Int64}}()
    for block ∈ blocks
        current_revadj = OrderedSet{Int64}()
        for i ∈ block.inputs
            if i ∈ keys(outmap)
                push!(current_revadj, outmap[i])
            end
        end
        push!(revadj, current_revadj)
    end
    return revadj
end

function topological_sort(adj, revadj; names=nothing)
    revdep = adj
    dep = [copy(s) for s ∈ revadj]
    nodeps = [n for (n, depset) ∈ enumerate(dep) if isempty(depset)]
    topsorted = Vector{Int64}()

    while !isempty(nodeps)
        n = pop!(nodeps)
        push!(topsorted, n)
        for n2 ∈ revdep[n]
            pop!(dep[n2], n)
            if isempty(dep[n2])
                push!(nodeps, n2)
            end
        end
    end

    if length(topsorted) != length(dep)
        cycle_ints = find_cycle(dep, setdiff(Set(collect(1:length(dep))), Set(topsorted)))
        @assert !isa(cycle_ints, Nothing)
        cycle = isempty(names) ? cycle_ints : [names[i] for i ∈ cycle_ints] 
        error("Topological sort failed: cyclic dependency $(join([String(n) for n ∈ cycle], " -> "))")
    end

    return topsorted
end

function find_cycle(dep, onlyset)
    dep = Dict{Int64, OrderedSet{Int64}}(k => (dep[k] ∩ onlyset) for k ∈ collect(1:length(dep)) if k ∈ onlyset)

    tovisit = Set{Int64}(keys(dep))
    stack = OrderedSet{Int64}()
    while !isempty(tovisit) | !isempty(stack)
        if !isempty(stack)
            n = stack[end]
            if !isempty(dep[n])
                n2 = pop!(dep[n])
                if n2 ∈ stack
                    i2loc = findall(x -> x==n2, stack)[1]
                    return vcat([s for s ∈ stack][i2loc:end], stack[i2loc])
                else
                    if n2 ∈ tovisit
                        pop!(tovisit, n2)
                        push!(stack, n2)
                    end
                end
            else
                pop!(stack, n)
            end
        else
            n = pop!(tovisit)
            push!(stack, n)
        end
    end
    return nothing
end

function visit_from_inputs(d::DAG, inputs)
    inputs = isa(inputs, Dict) ? keys(inputs) : inputs
    inputs = d.inputs ∩ inputs
    visited = OrderedSet{Int64}()
    doesBreak = false
    for (n, (block, parentset)) ∈ enumerate(zip(d.blocks, d.revadj))
        for i ∈ inputs
            if i ∈ block.inputs
                push!(visited, n)
                doesBreak = true
                break
            end
        end
        if !doesBreak && !isempty(visited ∩ parentset)
            push!(visited, n)
        end
    end
    return visited
end

function visit_from_outputs(d::DAG, outputs)
    outputs = d.outputs ∩ outputs
    visited = OrderedSet{Int64}()
    doesBreak = false
    for n ∈ reverse(collect(1:length(d.blocks)))
        block = d.blocks[n]
        childset = d.adj[n]

        for o ∈ outputs
            if o ∈ block.outputs
                push!(visited, n)
                doesBreak = true
                break
            end
        end
        if !doesBreak & isempty(visited ∩ childset)
            push!(visited, n)
        end
    end

    revVisited = OrderedSet{Int64}()
    for i ∈ reverse(collect(1:length(visited)))
        push!(revVisited, visited[i])
    end

    return revVisited
end

"maybe deprecate?"
function find_intermediate_inputs(blocks)
    required = OrderedSet()
    outmap = get_output_map(blocks)
    for (num, block) ∈ enumerate(blocks)
        if hasproperty(block, :inputs)
            inputs = block.inputs
        else
            inputs = OrderedSet(i for o ∈ block for i ∈ block[o])
        end
        for i ∈ inputs
            if i ∈ keys(outmap)
                push!(required, i)
            end
        end
    end
    return required
end
